1. Field of the Invention
The invention relates generally to the field of digital signal processing. More particularly, the invention relates to digital filtering for digital signal processing.
2. Discussion of the Related Art
Digital signal processing is an important aspect of digital communications. It may be used in communication applications such as satellite communication systems, satellite ranging systems (GPS, WAAS, GLONAS), radar systems, radio-locators for the military, and speech processing (such as processing a speech waveforms, when the input signal is of infinite duration), and restoration of a signal from noisy input.
Three important tools in signal processing are FIR filters, optimal Wiener filters, and correlation functions. Linear convolution is another tool that is realized in many processors, including industrially available processors such as: Universal processors and mobile devices' processors from Texas Instruments (Dallas, Tex.) and ST Microelectronics (Dallas, Tex.).
FIR Filters
Finite-length impulse response (FIR) filters are widely used. FIR filters may be important elements of most digital systems for the previously mentioned applications.
An 1-D FIR filter may be described by the linear convolution type equation
                                          y            ⁡                          (              n              )                                =                                    ∑                              k                =                0                                            M                -                1                                      ⁢                                                  ⁢                                          x                ⁡                                  (                                      k                    -                    n                                    )                                            ⁢                              h                ⁡                                  (                  k                  )                                                                    ,                                  ⁢                  n          =                      0            :                          (                              N                -                1                            )                                      ,                            (        1        )            where x(n) is an input signal of length L and h(k) is the impulse response characteristics of the filter that has a length M≧L. If N≧L+M−1, the cyclic convolution and linear convolution are identical.
As is known, the efficient realization of FIR filters is not provided by calculation in the time domain, especially for long data signals. The frequency-domain approach based on the discrete Fourier transform is a computational procedure that serves as an alternative to time-domain convolution, and it is computationally more efficient than time-domain convolution due to the existence of efficient algorithms for computing the DFT. These algorithms are called fast Fourier transform (FFT) algorithms.
Optimal Wiener Filters
A Wiener filter is defined as a filter that provides optimal estimate of original discrete signal x(n) from an observed noisy signal
                                          y            ⁡                          (              n              )                                =                                                    ∑                                  k                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                x                  ⁡                                      (                                          k                      -                      n                                        )                                                  ⁢                                  h                  ⁡                                      (                    k                    )                                                                        +                          n              ⁡                              (                n                )                                                    ,                                  ⁢                  n          =                      0            :                          (                              N                -                1                            )                                      ,                            (        2        )            where n(n) is noise. The optimality is with respect to mean-square error and the estimate is defined as the linear cyclic convolution
                                                        x              ^                        ⁡                          (              n              )                                =                                    ∑                              k                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          w                ⁡                                  (                  k                  )                                            ⁢                              y                ⁡                                  (                                      k                    -                    n                                    )                                                                    ,                                  ⁢                  n          =                      0            :                          (                              N                -                1                            )                                      ,                            (        3        )            where w(k) is the impulse response function of the Wiener filter. The filtering in equation (3) is implemented in the Fourier domain, {circumflex over (X)}(ω)=W(ω)Y(ω), by the filter with transfer function
                                          W            ⁡                          (              ω              )                                =                                                    H                _                            ⁡                              (                ω                )                                                                                                                            H                    ⁡                                          (                      ω                      )                                                                                        2                            +                                                ϕ                                      n                    /                    x                                                  ⁡                                  (                  ω                  )                                                                    ,                                  ⁢                  ω          =                      0            :                          (                              N                -                1                            )                                      ,                            (        4        )            where H(ω) is the DFT of h(k) and φn/x (ω), the noise-signal ratio. {circumflex over (X)}(ω) and Y(ω) are the Fourier transforms of {circumflex over (x)}(n) and y(n) respectively.
The realization of optimal filtering requires three DFTs and N multiplications to calculate {circumflex over (X)}(ω). Therefore, the total number of multiplications required to perform optimal filtration by the DFT method can be estimated as3[N/2(log2 N−3)+2]+N+3N=3N/2(log2 N−3)+4N+6.where 3N operations are assumed for calculation of the optimal filter in equation (4).Cross-Correlation
Cross-correlation between two discrete sequences or signals x(n) and h(n) is defined as
                              r          ⁡                      (            n            )                          =                              1            N                    ⁢                                    ∑                              k                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          x                ⁡                                  (                  k                  )                                            ⁢                              h                ⁡                                  (                                      k                    +                    n                                    )                                                                                        (        5        )            
The data sequences may be either correlated or convolved simply by reversing the order of one of the data sequences. Thus, the correlation and convolution can be calculated by the same program simply by reversing one of the sequences.
The correlation computation may be speeded by using the DFT approach because in the Fourier domain the correlation takes the following formR(ω)=X(ω)Ĥ(ω), ω=0:(N−1).  (6)
The correlation realization by the FFT requires the same number of operations as for the linear convolution. For longer data sequences, the fast DFT method may be used to achieve fast correlation.
FFT Method of Convolution Realization
The DFT provides a discrete frequency representation of the finite-duration sequence (signal) in frequency domain and it reduces the cyclic convolution of two sequences to the simple operation of the multiplication of their Fourier transformsY(p)=X(p)H(p)  (7)where Y(p), X(p), and H(p) are the discrete Fourier transforms of y(n), x(n), and h(k), respectively.
The discrete Fourier transform, X(p), of the signal x(t), of length N, is multiplied by the frequency characteristics, H(p), of a linear filter. And then the inverse discrete Fourier transform, F−1, is used, which results in the filtered signal, Y(t). A diagram of the Fourier method is shown in blocks 100-105 depicted in FIG. 1A.r(t)→F[r](p)=X=(p)→X(p)H(p)=Y(p)→F−1[Y(p)](t)=y(t)
The DFT may be performed twice (the DFT performance is not considered for the H(p)). This approach uses N values of the frequency characteristics and requires N operations of complex multiplication in the frequency domain and N−1 additions. Additionally, direct and inverse DFTs require N/2 (log2 N−3)+2 complex multiplications. Therefore, the traditional FFT method of the linear filtration requiresMN=2[N/2(log2N−3)+2]+N=N(log2N−2)+4.  (8)complex multiplications, and aboutAN=2N(log2N−2)  (9)operations of additions. Here, the case of most interest in practice is considered, when the length of the signal is N=2r, r>1.
If one assumes that the complex multiplication is performed by three real multiplications and three additions, then the numbers of real operations of multiplications and additions can be estimated as3MN=3N(log2N−2)+9, 3AN=6N(log2N−2).  (10)The FFT-based method of realization of the convolution is superior from a computational point of view.Other Methods
Some disadvantages of applying the DFT are in the use of trigonometric functions cosine and sine functions, and other complex arithmetic functions. To avoid such disadvantages, different algebraic methods have been proposed. Among them are the overlap-saved and overlap-add methods and the nesting of polynomials. These algorithms represent 1-D convolution as multi-dimensional convolutions which are reduced to computation of small length convolutions and polynomial multiplications. These algorithms require fewer arithmetic operations than the FFT approach for small sequence length N<200. This is due to the fact that the number of multiplications per sample for these algorithms equals (3/2)r for N=2r, and this number grows exponentially faster than the linear estimate (3r−2) for the DFT. Therefore, these algorithms do not provide the fast performance of the FIR filter for long data.
The requirements for a fast and simple convolution process for long signals have not been fully met. What is needed is a solution that addresses both of these requirements.